#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/21
# @Author   :Changshu
# @File     :Exercise_606.py

# 606. 根据二叉树创建字符串
# 你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
# 空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对

# Definition for a binary tree node.
class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

class Solution:
	'''法一：递归，抄袭的代码，写的真好
		四种情况：
			1.左右子树都非空，左右子树都加上括号
			2.左子树非空，右子树空，左子树加上括号
			3.左子树空，右子树非空，左右子树都加上括号
			4.左、右子树都为空，都不加括号

	def tree2str(self, t: TreeNode) -> str:
		def dfs(root:TreeNode)->str:
			if not root:
				return ''
			leftStr=dfs(root.left)
			rightStr=dfs(root.right)
			if leftStr=='' and rightStr=='':
				return str(root.val)
			res=''
			res+=str(root.val)
			res+='('+leftStr+')'
			if rightStr!='':
				res+='('+rightStr+')'
			return res
		res=dfs(t)
		return res
	'''

	'''法二：迭代法'''
	def tree2str(self, t: TreeNode) -> str:
		if not t:
			return ''
		stack=[t]
		visited=set()
		res=[]
		while len(stack):
			node=stack[-1]
			if visited.__contains__(node):
				res.append(')')
				stack.pop()
			else:
				visited.add(node)
				res+='('+str(node.val)
				if not node.left and node.right:
					res.append('()')
				if node.right:
					stack.append(node.right)
				if node.left:
					stack.append(node.left)

		return ''.join(res[1:len(res)-1])

if __name__ == '__main__':
	''' 测试通过
	root=TreeNode(1)
	node2_1=TreeNode(2)
	node2_2 = TreeNode(3)
	node3_1 = TreeNode(4)

	root.left=node2_1
	root.right=node2_2
	node2_1.left=node3_1

	solution=Solution()
	print(solution.tree2str(root))
	'''

	root = TreeNode(1)
	node2_1 = TreeNode(2)
	node2_2 = TreeNode(3)
	node3_1 = TreeNode(4)

	root.left = node2_1
	root.right = node2_2
	node2_1.right = node3_1

	solution = Solution()
	print(solution.tree2str(root))